有nn个红球，mm个蓝球，从中选出xx个红球和yy个蓝球排成一排的得分是ax⋅bya_x \cdot b_y，其中a0=b0=1a_0 = b_0 = 1

设f(t)f(t)表示恰好取出tt个球排成一排的所有局面的得分之和

两个局面相同，当且仅当这两排球的个数相等，且在对应列位置上的颜色都是相同的

求所有满足f(t)f(t)为奇数的t2t^2之和

n,m≤220n, m\le 2^{20}

51nod 1824

Solution

就是要求：

第一反应是直接卷，但是模2肯定不能FFT

根据Lucas定理，(nm)\displaystyle \binom{n}{m}在模22意义下的值就是nn和mm二进制下每一位的组合数相乘

因此，

那么原式就变成了

f(t)=∑i⊆taibt−i f(t) = \sum_{i\subseteq t}a_ib_{t - i}

这就是子集卷积的形式了

但是这里n+mn + m有2212^{21}，直接O(nlog2n)O(n\log^2 n)的子集卷积是过不了的。

提两个改动比较大的优化：

  • DWT中因为(x + y) % MOD和(y - x + MOD) % MOD在模2意义下都是x ^ y，所以可以放一起写

  • 压位，从O(nlog2n)O(n\log^2 n)优化到O(nlogn)O(n \log n)

    把原来需要开f[21][2^21]的数组的信息压到f[2^21]中，即把第一维压到值里（因为原本的值只有0/1）这样做并不会影响DWT的运算，因为有了上一个优化后，DWT是按位异或的

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = ((1 << 20) << 1) + 5;

int N, M;
int A[Maxn], B[Maxn];

inline void DWT (int *A, int n)
{
	for (int mid = 1; mid < n; mid <<= 1)
		for (int i = 0, len = mid << 1; i < n; i += len)
			for (int j = i; j < i + mid; ++j)
				A[j + mid] = A[j] ^ A[j + mid];
}

int cnt[Maxn], pw2[Maxn];

inline void Solve ()
{
	static int f[Maxn], g[Maxn], h[Maxn];

	int n = 1, lg = 0; pw2[0] = 1;
	while (n <= N + M) n <<= 1, pw2[++lg] = n;

	for (int i = 1; i < n; ++i) cnt[i] = cnt[i >> 1] + (i & 1);

	for (int i = 0; i <= N; ++i) if (A[i] & 1) f[i] = pw2[cnt[i]];
	for (int i = 0; i <= M; ++i) if (B[i] & 1) g[i] = pw2[cnt[i]];

	DWT (f, n), DWT (g, n);

	for (int S = 0; S < n; ++S)
		for (int j = 0; j <= lg; ++j) if ((f[S] >> j) & 1)
		{
			for (int i = j; i <= lg; ++i)
				if ((g[S] >> (i - j)) & 1)
					h[S] ^= pw2[i];
		}

	DWT (h, n);

	LL ans = 0;
	for (int i = 1; i < n; ++i)
		if (h[i] & pw2[cnt[i]])
			ans += (LL) i * i;

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>();

	static char S[Maxn];
	scanf("%s", S + 1);
	for (int i = 1; i <= N; ++i) A[i] = S[i] - '0';
	scanf("%s", S + 1);
	for (int i = 1; i <= M; ++i) B[i] = S[i] - '0';
	A[0] = B[0] = 1;

}

int main()
{

#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}